package 贪心;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 使有效括号最少添加.java
 * @Description TODO
 * @createTime 2020年10月22日 21:09:00
 * 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
 *
 * 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
 *
 * 它是一个空字符串，或者
 * 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
 * 它可以被写作 (A)，其中 A 是有效字符串。
 * 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入："())"
 * 输出：1
 * 示例 2：
 *
 * 输入："((("
 * 输出：3
 *
 *  //用left记录左括号  res记录右括号
 *    //两个互相匹配就是消耗 一个右括号可以消耗一个左括号 看最后还剩下多少不能配对的
 */
public class 使有效括号最少添加 {
    class Solution {
        //用left记录左括号  res记录右括号
        //两个互相匹配就是消耗 一个右括号可以消耗一个左括号 看最后还剩下多少不能配对的
        public int minAddToMakeValid(String S) {
            int left = 0, res = 0;
            for(char ch : S.toCharArray()){
                if(ch == '('){
                    left++;
                }else {
                    if(left > 0){
                        left--;
                    }else {
                        res++;
                    }
                }
            }
            return res + left;
        }

    }
}
